#include "LinkStack.h"
#include <stdio.h>
#include <stdlib.h>


//1）初始化一个链式栈，并将栈的地址返回 
LinkStack * InitStack()
{
    //创建一个链式栈（头结点），并初始化
    LinkStack * s = (LinkStack *)malloc( sizeof(LinkStack) );
    s->top = NULL;  
    s->bottom = NULL;
    s->num = 0;

    return s;
}

//2）清空栈 
void ClearStack( LinkStack * s )
{
    //栈不存在 || 栈为空 
    if( s == NULL || s->top == NULL )
    {
        return ;
    }

    //清空：释放栈中的每一个数据节点 --> 遍历 
    Dgamenode * p = s->top;     //遍历指针 
    while( p )
    {
        //删除栈顶元素top（表尾，最后一个节点）
        s->top = s->top->prev;
        if( s->top != NULL )
        {
            s->top->next = NULL;
        }
        p->prev = NULL;

        free( p );

        p = s->top;     //继续释放下一个
    }

    s->top = NULL;
    s->bottom = NULL;
    s->num = 0;
}

//3）销毁栈 
void DestroyStack( LinkStack * s )
{
    //栈不存在
    if( s == NULL )
    {
        return ;
    }

    //清空：释放栈中的每一个数据节点 --> 遍历 
    ClearStack( s );

    //最后释放栈头结点
    free( s );
}

//4）判断是否为空栈 
int IsEmpty( LinkStack * s )
{
    //栈不存在 || 栈里面没有元素
    if( s == NULL  || s->num == 0 )
    {
        return 1;
    }
    return 0;
}

//5）栈的长度（元素个数）
int StackLength( LinkStack * s )
{
    if( s == NULL )
    {
        return 0;
    }
    return s->num;
}

//6）入栈 
int Push( LinkStack * s, GameType dx , GameType dy )
{
    //不能入栈的情况：栈不存在 
    if( s == NULL )
    {
        return 0;
    }

    //为入栈的元素，创建一个新的数据节点，并初始化 
    Dgamenode * pnew = (Dgamenode *)malloc( sizeof(Dgamenode) );
    pnew->datax = dx;
    pnew->datay = dy;
    pnew->next = NULL;
    pnew->prev = NULL;
    
    //入栈，只能在栈顶top(表尾)进行插入或者删除操作 ---> 尾插法 
    if( s->top == NULL )   //从无到有 
    {
        s->top = pnew;
        s->bottom = pnew;
    }
    else    //从少到多
    {
        //尾插法 
        s->top->next = pnew;
        pnew->prev = s->top;
        s->top = pnew;
    }

    s->num++;   //元素个数+1 
    printf("dx=%d dy=%d\n",dx,dy);
    return 1;
}

//7）出栈 
int Pop( LinkStack * s , hq *pnew )
{
    //不能出栈的情况：栈不存在 || 栈为空 
    if( s == NULL || s->num == 0 )
    {
        return 0;
    }

    //出栈 
        //保存出栈元素的值
        pnew->x = s->top->datax;
        pnew->y= s->top->datay;
        //释放该栈顶元素的空间（删除节点） 
        Dgamenode * p = s->top;     //指向要释放的栈顶元素 

        s->top = s->top->prev;
        if( s->top != NULL )
        {
            s->top->next = NULL;
        }
        p->prev = NULL;

        free( p );

        s->num--;       //元素个数-1

    if( s->num == 0 )
    {
        s->top = NULL;
        s->bottom = NULL;
    }
    printf("chuzhan dx=%d chuzhan dy=%d\n", pnew->x, pnew->y);
    return 1;
}

//8）获取栈顶元素，但是不出栈 
int GetTop( LinkStack * s , hq *pnew )
{
    //不能出栈的情况：栈不存在 || 栈为空
    if( s == NULL || s->num == 0 )
    {
        return 0;
    }

    //获取栈顶元素的值，但是不出栈
        //只需要保存栈顶元素的值即可 
        pnew->x = s->top->datax;
        pnew->y= s->top->datay;

    return 1;
}
